package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/7/31 15:56
 */
public class ReverseBetween_92 {

    public ListNode reverseBetween(ListNode head, int m, int n) {
        // m = n 直接返回
        if (head == null || m == n) return head;
        ListNode cur = head, pre = null;
        // 题目中没有说val代表坐标，所以通过pos去寻找
        int pos = 1;
        // 分别找到在m的节点和在m前一位的节点
        // 当m = 1的时候代表是从头结点开始反转
        while (pos < m) {
            pre = pre == null ? head : pre.next;
            cur = cur.next;
            pos++;
        }
        // 执行链表的反转操作，需要进行记录的节点包括
        // pre2 -- 部分反转链表，反转后的头结点
        // temp -- 原链表的下一个结点
        // tale -- 反转链表，反转完毕的尾结点
        ListNode pre2 = null, temp = null, tale = cur;
        while (pos <= n) {
            temp = cur.next;
            cur.next = pre2;
            pre2 = cur;
            cur = temp;
            pos++;
        }
        // 如果pre不为空，则代表m>1
        if (pre != null) pre.next = pre2;
            // 链表为空则代表m=1，这时替换头结点即可
        else head = pre2;
        // 链接尾结点
        tale.next = temp;
        return head;
    }


    // 反转m ~ n的链表
    public ListNode reverseBetween2(ListNode head, int m, int n) {
        if (m == 1) return reverseN(head, n);
        // 一边去找遍历开始的节点，找到过后开始进行遍历
        // m - 1 去找遍历开始的节点
        // n - 1不断记录需要反转的个数
        head.next = reverseBetween2(head.next, m - 1, n - 1);
        return head;
    }

    // 后继节点
    ListNode successor;

    // 反转head开始的n个结点
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 反转到头，记录此时的后驱结点
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        // 让head的下一个结点指向自己
        head.next.next = head;
        // 将head指向后驱元素
        head.next = successor;
        return last;
    }

    // 反转整个链表
    public ListNode reverse(ListNode head) {
        // 排除给定的节点就是头结点的情况
        if (head == null || head.next == null) return head;
        ListNode last = reverse(head.next);
        // 精髓，把下一个节点的next指针指向当前结点
        // 是一致下一个结点全部是已反转的链表
        head.next.next = head;
        head.next = null;
        return last;
    }

    private ListNode reverseN(int n, ListNode head) {
        if (n == 1) {
            // 遍历到头的时候，记录后继节点的位置
            successor = head.next;
            return head;
        }
        final ListNode node = reverseN(n - 1, head.next);
        head.next.next = head;
        // 指向后继元素
        head.next = successor;
        return node;
    }

    // 如果要对链表做局部修改。需要进行一下几步
    private ListNode reverseBetween(int m, int n, ListNode head) {
        // 边界处理
        // 题目中是从1开始的
        if (m == 1) return reverseN(head, n);
        // 1.修改链条
        head.next = reverseBetween(m - 1, n - 1, head.next);
        // 2.返回头结点
        return head;
    }

    static class Solution {
        ListNode successor;

        public ListNode reverseBetween(ListNode head, int m, int n) {
            if (m == 1) {
                return reverseN(head, n);
            }
            head.next = reverseBetween(head.next, m - 1, n - 1);
            return head;
        }

        private ListNode reverseN(ListNode head, int n) {
            if (n == 1) {
                // 记录后继节点的位置
                successor = head.next;
                return head;
            }
            ListNode node = reverseN(head.next, n - 1);
            head.next.next = head;
            head.next = successor;
            return node;
        }

    }

}
